/**
 * 快速排序（Quick Sort）是一种高效的排序算法，采用分治策略来对一个数组进行排序。以下是其基本步骤：
 * - 选择基准值：从数组中挑选一个元素作为“基准”（pivot）。
 * - 分区操作：重新排列数组，使得所有比基准小的元素都排在基准的前面，所有比基准大的元素都排在基准的后面。这个过程称为分区（partition）操作。
 * - 递归排序子数组：递归地将小于基准值的子数组和大于基准值的子数组进行快速排序。
 * 快速排序的特点
 * - 时间复杂度：平均情况下为 O(n log n)，最坏情况下为 O(n^2)。
 * - 空间复杂度：O(log n)，因为递归调用栈会占用额外的空间。
 * - 稳定性：不是稳定的排序算法，相同元素的相对位置可能会改变。
 */

const arr1 = [5, 7, 1, 6, 8, 3, 2, 9, 4];
const arr2 = [5, 7, 1, 6, 8, 3, 2, 9, 4];

/**
 * 快速排序算法的递归实现
 * 通过选择一个基准元素，将数组分为两部分，一部分包含小于基准的元素，另一部分包含大于基准的元素
 * 然后对这两部分递归进行快速排序，最终达到整个数组的排序
 *
 * @param {Array} arr - 需要排序的数组
 * @param {boolean} mode - 排序的模式，默认为true，表示正序，false表示倒序
 * @param {number} left - 排序开始的左边界，默认为数组的起始位置
 * @param {number} right - 排序结束的右边界，默认为数组的末尾位置
 * @returns {Array} - 返回排序后的数组
 */
function quickSort(arr, mode = true, left = 0, right = arr.length - 1) {
  // 如果左边界大于等于右边界，说明已经没有元素需要排序，直接返回数组
  if (left >= right) return arr;
  
  // 调用partition函数，将数组分为两部分，并获取基准元素的索引
  const middle = partition(arr, mode, left, right);
  
  // 递归对基准元素左侧的数组进行快速排序
  quickSort(arr, mode, left, middle - 1);
  
  // 递归对基准元素右侧的数组进行快速排序
  quickSort(arr, mode, middle + 1, right);
}


/**
 * 将数组按照某个基准值划分为两部分，所有小于基准值的元素移动到基准值的左边，所有大于基准值的元素移动到基准值的右边
 * 此函数通常用于快速排序算法的一部分
 * @param {Array} arr - 待划分的数组
 * @param {boolean} mode - 排序的模式，默认为true，表示正序，false表示倒序
 * @param {number} left - 划分的起始索引
 * @param {number} right - 划分的结束索引
 * @returns {number} - 基准值的最终索引
 */
function partition(arr, mode = true, left, right) {
  // 初始化左指针
  let leftIdx = left;
  // 获取右指针的值，作为基准值
  let rightVal = arr[right];
  // 遍历数组，将小于基准值的元素放到左边
  for (let i = leftIdx; i < right; i++) {
    let _mode = mode ? arr[i] < rightVal : arr[i] > rightVal;
    if (_mode) {
      // 如果当前元素小于基准值，将其与leftIdx位置的元素交换，并将leftIdx右移
      [arr[i], arr[leftIdx]] = [arr[leftIdx], arr[i]];
      leftIdx++;
    }
  }
  // 将基准值放到正确的位置，即leftIdx
  [arr[right], arr[leftIdx]] = [arr[leftIdx], arr[right]];
  // 返回基准值的最终索引
  return leftIdx;
}


quickSort(arr1);
console.log("▶『正序』", arr1);
quickSort(arr2, false);
console.log("▶『倒序』", arr2);


/**
 * 执行过程模拟(正序)
 * quickSort([5, 7, 1, 6, 8, 3, 2, 9, 4], 0, arr.length-1) 传入数组 开始的idx为0 结束的idx为arr.length-1
 * leftIdx=0 rightVal=4 记录开始的idx为0 以及基准值4
 * i0 5<4 对比 arr[0]<4 不小于不做任何处理
 * i1 7<4 对比 arr[1]<4 不小于不做任何处理
 * i2 1<4 对比 arr[2]<4 交换值的位置 [arr[i],arr[leftIdx]]=[arr[leftIdx],arr[i]] [1, 7, 5, 6, 8, 3, 2, 9, 4] leftIdx=0+1=1
 * i3 6<4 不小于不做任何处理
 * i4 8<4 不小于不做任何处理
 * i5 3<4 对比 arr[5]<4 交换值的位置 [arr[i],arr[leftIdx]]=[arr[leftIdx],arr[i]] [1, 3, 5, 6, 8, 7, 2, 9, 4] leftIdx=1+1=2
 * i6 2<4 对比 arr[6]<4 交换值的位置 [arr[i],arr[leftIdx]]=[arr[leftIdx],arr[i]] [1, 3, 2, 6, 8, 7, 5, 9, 4] leftIdx=1+1=3
 * i7 9<4 不小于不做任何处理
 * [arr[right],arr[leftIdx]]=[arr[leftIdx],arr[right]] 将基准值放到正确的位置 [1, 3, 2, 6, 8, 7, 5, 9, 4]
 * return leftIdx=3
 *
 * 递归以基准值的位置将数组分为左右两个部分继续调用
 * quickSort([1, 3, 2, 6, 8, 7, 5, 9, 4], 0, leftIdx-1)
 * quickSort([1, 3, 2, 6, 8, 7, 5, 9, 4], leftIdx+1, arr.length-1)
 */
